package 链表.链表排序;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/4/19 17:05
 * @description:
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode head = new ListNode(-1,new ListNode(5,new ListNode(3,new ListNode(4,new ListNode(0)))));
        System.out.println(sortList2(head).val);
    }
    //不能用冒泡排序，可以使用直接插入排序 但是此方法超时
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode root = new ListNode(-100);
        root.next = head;
        ListNode pre = root;
        ListNode p = root.next.next;
        ListNode q = new ListNode();
        root.next.next = null;
        while (p != null) {
            while (pre.next != null && pre.next.val < p.val) {
                pre = pre.next;
            }
            q = p.next;
            p.next = pre.next;
            pre.next = p;
            p = q;
            //这里不能少了！
            pre = root;
        }
        return root.next;
    }


    //归并排序 先分割再merge TODO 重要
    public static ListNode sortList2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        //快慢指针 fast指针移动到链表尾端 slow指针移动到链表中间
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        //将链表一分为二
        slow.next = null;
        ListNode left = sortList2(head);
        ListNode right = sortList2(tmp);
        //定义一个头结点，方便节点的插入
        // h 就是尾指针
        ListNode h = new ListNode(0);
        ListNode res = h;
        //链表的归并
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        //merge非递减序列最后，可以这样来合并剩余部分的链表
        h.next = left != null ? left : right;
        return res.next;
    }

    public static ListNode test(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null || fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        ListNode left = test(head);
        ListNode rigth = test(tmp);
        ListNode res = new ListNode(0);
        ListNode r = res;
        while (left != null && rigth != null) {
            if (left.val < rigth.val) {
                r.next = left;
                left = left.next;
            } else {
                r.next = rigth;
                rigth = rigth.next;
            }
            r = r.next;
        }
        r.next = left != null ? left : rigth;
        return res;
    }
}
